1) Field of the Invention
This invention relates to a dividing apparatus for use with a data processing apparatus for dividing a dividend by a divisor both in the form of decimal data represented in binary-coded decimal notation (BCD).
2) Description of the Related Art
Generally, in a data processing apparatus, decimal data are represented in binary-coded decimal notation. In order to divide a dividend by a divisor both in the form of such decimal data, similarly as in calculation with figures written down on paper, the place positions of uppermost digits of the two operands (dividend and divisor) which are not equal to zero are adjusted to each other (leftward place adjustment), and a quotient is calculated successively for different digits beginning with the uppermost place digit to obtain a final quotient. Accordingly, the speed of decimal division can be raised by decreasing the time required for calculation of a quotient of a certain one digit.
Here, the following two methods are listed as the most basic method for calculating a quotient of each digit.
1. A divisor is successively subtracted from a dividend or an intermediate remainder (the terminology "intermediate remainder" is hereinafter used as far as there is no need of particularly distinguishing a divisor and an intermediate remainder from each other) while the number of times of such division is counted until after the result of subtraction becomes a negative value, and a quotient is determined based on the count value.
2. A quotient forecasting circuit or a quotient forecasting table is prepared in advance, and a quotient of one digit is forecast based on several upper bits of an intermediate remainder and a divisor by the quotient forecasting circuit or using the quotient forecasting table, whereafter a multiple or multiples of the divisor prepared in advance or a multiple of the divisor obtained by combining such multiples and corresponding to the forecast quotient is subtracted from the dividend and then the forecast quotient is corrected in accordance with the positive or negative sign of the result of subtraction.
With the first method described above, when the quotient is "0", at least one time of subtraction processing is required; when the quotient is "1", two times of subtraction processing are required; . . . ; when the quotient is "8", nine times of subtraction processing are required; and when the quotient is "9", nine times of subtraction processing (the quotient is never equal to 10) are required. Accordingly, the minimum number of cycles required for calculation processing for a quotient of one digit is 5.4 on the average and 9 in the maximum.
With the first method described above, as the value of the quotient increases, the number of subtraction calculations increases, and accordingly, high speed decimal division can be achieved by reducing the number of quotient calculation cycles to reduce the processing time when the value of the quotient is high.
For example, if a five-fold multiple of the divisor is prepared with the average value of the quotient regarded as "5" and it is checked whether or not the quotient in quotient calculation processing is equal to or higher than "5", that is, whether or not an intermediate remainder is equal to or higher than five times the divisor and then, when the quotient is equal to or higher than "5", the five-fold multiple is subtracted from the intermediate remainder, whereafter repetitive subtraction calculations of the divisor are performed (refer to, for example, Japanese Patent Laid-Open Application No. Showa 58-132837), then when the quotient is "0", a quotient of one digit can be calculated by two times of subtraction processing; when the quotient is "1", a quotient of one digit can be calculated by three times of subtraction processing; when the quotient is "2", a quotient of one digit can be calculated by four times of subtraction processing; when the quotient is "3", a quotient of one digit can be calculated by five times of subtraction processing; when the quotient is "4", a quotient of one digit can be calculated by five times of subtraction processing; when the quotient is "5", a quotient of one digit can be calculated by two times of subtraction processing; when the quotient is "6", a quotient of one digit can be calculated by three times of subtraction processing; when the quotient is "7", a quotient of one digit can be calculated by four times of subtraction processing; when the quotient is "8", a quotient of one digit can be calculated by five times of subtraction processing; and when the quotient is "9", a quotient of one digit can be calculated by five times of subtraction processing. Accordingly, in this instance, the minimum number of cycles required for calculation processing for a quotient of one digit can be reduced to 3.8 on the average and to 5 in the maximum.
In order to further reduce the number of repetitive subtraction operations required for calculation of a quotient of one digit, several times of subtraction of a divisor should be reduced to one time of subtraction. In particular, while a multiple or multiples of the divisor must be used, in this instance, the kinds of required multiples and the algorithm for selecting a multiple to be subtracted matter.
Generally, it is a common algorithm for calculating a quotient of one digit that, taking notice of the fact that, in a data processing apparatus, a decimal number is represented by a binary-coded decimal number of 4 bits and the weight of 4 bits is 8, 4, 2, 1 in order beginning with the most significant bit, an eight-fold multiple, a four-fold multiple, a two-fold multiple and a one-fold multiple of a divisor are prepared in advance, and subtraction from a dividend is performed in order for the multiples beginning with a multiple corresponding to the most significant bit of the individual bits of a quotient of one digit, that is, in the order of the eight-fold multiple, the four-fold multiple, the two-fold multiple and the one-fold multiple, and if the result of the subtraction is in the positive in sign, then the corresponding bit of the quotient is turned on to calculate a quotient of one digit (refer to, for example, Japanese Patent Laid-Open Application No. Showa 55-82352).
Here, since the quotient is equal to or lower than "9", if the result of first time subtraction of the eight-fold multiple is in the positive in sign, then there is no need of subsequently subtracting the four-fold multiple, but it is sufficient if only subtraction of the one-fold multiple is performed. Accordingly, the minimum number of times of subtraction of multiples required for calculation of a quotient of one digit is four when the quotient is within the range from "0" to "7", but is two when the quotient is "8" or "9", and accordingly is 3.6 on the average and 4 in the maximum.
It is to be noted that also another decimal dividing method which adopts the same quotient calculation algorithm as that described above except that subtraction of the eight-fold multiple in the processing described above is realized by subtraction of the four-fold multiple by two times (accordingly, three kinds of multiples including a four-fold multiple, a two-fold multiple and a one-fold multiple are used) has been proposed (refer to, for example, Japanese Patent Laid-Open Application No. Showa 57-111738).
With the dividing method which employs the first method described hereinabove, however, in a circumstance at present, in order to settle a quotient of one digit, four times of subtraction in the maximum and 3.6 times of subtraction on the average are required in the minimum case, and the processing time is comparatively long. Thus, it is demanded to further reduce the processing time to achieve higher speed decimal division.
On the other hand, with the second method described hereinabove, the number of times of subtraction can be reduced to once by using a forecast quotient which is equal to or greater by one than a correct quotient. However, if it is tried to construct the quotient forecasting table, for example, with a memory circuit and to look up a value in the quotient forecasting table using three upper digits (12 bits) of an intermediate remainder and two upper digits (8 bits) of a divisor in order to store a value equal to or greater by one than a correct value as a forecast quotient, where the forecast quotient is constituted from 4 bits, a memory capacity of up to 4 bits.times.1,024 Kwords is required. Consequently, a considerable circuit area is required for the memory, and as the capacity of the memory increases, an increased sufficient read time is required. After all, much processing time is required.
In the meantime, if it is tried to construct the quotient forecasting circuit using logic gates without using a memory circuit, the logic is complicated, which increases the difficulty in designing, and besides, a great number of logic stages are required.
Thus, since a delay time required to forecast a quotient invites an increase of machine cycles in any case, it is actually practical to divide a machine cycle into at least two cycles of a quotient forecasting cycle and a subtraction cycle.
Accordingly, where a forecast quotient is used as in the second method described above, even if correction of a quotient based on the positive or negative sign of a result of subtraction is executed in an overlapping condition with the quotient forecasting cycle for a next digit, two cycles are required for calculation of a quotient of one digit.
Further, with any of the first and second methods described above, when excessive subtraction occurs with a result of subtraction, a further one cycle is required with a restore method wherein a one-fold multiple of a divisor is added to an intermediate remainder, but with a non-restore method wherein processing of adding a one-fold multiple of a divisor is performed substantially in a next quotient calculation cycle, since addition correction of the divisor is additionally performed depending upon whether or not excessive subtraction has occurred in the last quotient calculation processing, the control is further complicated.
As can be .recognized from the foregoing, while it is possible to reduce the time required for calculation of a quotient of one digit to two or three cycles using a forecast quotient, there is a subject to be solved in that the circuit area required to obtain a forecast quotient or the complication in circuit designing is increased.